package com.datastructure.test.find132subseq;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Find132SubSeq {

    public static void main(String[] args) {
        Find132SubSeq find132SubSeq = new Find132SubSeq();
        ArrayList<Integer> nums= null;
        boolean subseq = find132SubSeq.find132Subseq(nums);
        System.out.println(subseq);
    }

    public boolean find132Subseq (ArrayList<Integer> nums) {
        // write code here
        for (int i = 0; i < nums.size(); i++) {
            if(i>0&& nums.get(i).equals(nums.get(i - 1))){
                continue;
            }
            int j = i+1;
            while (j< nums.size()&&nums.get(i)<nums.get(j)){
                if(j>i+1&&nums.get(j).equals(nums.get(j-1))){
                    continue;
                }
                int k = j+1;
                while (k< nums.size()){
                    if(k>j+1&&nums.get(k).equals(nums.get(k-1))){
                        continue;
                    }
                    if(nums.get(i)<nums.get(k)&&nums.get(j)>nums.get(k)){
                        return true;
                    }
                    k++;
                }
                j++;
            }
        }
        return false;
    }

    public boolean find132Subseq2 (ArrayList<Integer> nums) {
        // write code here
        ArrayDeque<Integer> stack = new ArrayDeque<>(nums.size());
        int t = Integer.MIN_VALUE;
        for (int i=nums.size() - 1; i>=0; --i) {
            if (nums.get(i) < t) return true;
            while (!stack.isEmpty() && stack.peek() < nums.get(i)) {
                t = stack.pop();
            }
            stack.push(nums.get(i));
        }
        return false;
    }
}
